// https://leetcode.cn/problems/course-schedule/

// 算法思路总结：
// 1. 拓扑排序检测有向图是否存在环
// 2. 构建邻接表和入度数组表示课程依赖关系
// 3. 从入度为0的节点开始进行广度优先遍历
// 4. 统计可完成课程数量判断是否能修完所有课程
// 5. 时间复杂度：O(V+E)，空间复杂度：O(V+E)

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <cstring>

class Solution 
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        unordered_map<int, vector<int>> edges;
        vector<int> in(numCourses, 0);

        for (const auto& v : prerequisites)
        {
            int src = v[1], dst = v[0];
            edges[src].push_back(dst);
            in[dst]++;
        }

        queue<int> q;
        for (int i = 0 ; i < numCourses ; i++)
        {
            if (in[i] == 0)
            {
                q.push(i);
            }
        }

        int count = 0;
        while (!q.empty())
        {
            int V = q.front();
            q.pop();
            count++;

            for (const int& dst : edges[V])
            {
                if (--in[dst] == 0)
                {
                    q.push(dst);
                }
            }
        }

        return count == numCourses;
    }
};

int main()
{
    int numCourses1 = 2, numCourses2 = 2;
    vector<vector<int>> prerequisites1 = {{1,0}}, prerequisites2 = {{1,0},{0,1}};

    Solution sol;

    cout << (sol.canFinish(numCourses1, prerequisites1) == 1 ? "True" : "False") << endl;
    cout << (sol.canFinish(numCourses2, prerequisites2) == 1 ? "True" : "False") << endl;

    return 0;
}